Ročníková práca - triediace algoritmy¶

V tejto ročníkovej práci sa budem zaoberať triediacimi algoritmami. Vysvetlím, čo sú to triediace algoritmy, prečo sú dôležité a aké sú ich základné vlastnosti. Taktiež sa pozriem na niektoré z najznámejších triediacich algoritmov a porovnám ich efektívnosť a zložitosť.


Metodika práce¶

  1. Vytvorenie testovacej funkcie

  2. Vytvorenie jednotlivých triediacich algoritmov

  3. Vytvorenie vizualizačnej funkcie

  4. Vizualizácia jednotlivých triediacich algoritmov

  5. Vytvorenie porovnávacej funkcie

  6. Porovnanie jednotlivých triediacich algoritmov


Cieľ práce¶

Porovnať a analyzovať niektoré z najznámejších triediacich algoritmov a zistiť, ktorý z nich je najefektívnejší a najvhodnejší pre rôzne typy dát a veľkosti problémov.


Úvod¶

Triedenie je základná operácia v informatike a zohráva kľúčovú úlohu v rôznych aplikáciách, od jednoduchých úloh správy dát po komplexné algoritmické problémy. V jeho podstate triedenie znamená usporiadanie kolekcie položiek podľa určitých kritérií.


Dôležitosť triedenia¶

Význam triediacich algoritmov vyplýva z ich všadeprítomného použitia v každodennom živote a ich nevyhnutnej úlohy v počítačovom programovaní a vývoji softvéru. Tu sú niektoré kľúčové dôvody, prečo je triedenie dôležité:

  1. Organizácia dát: Triedenie umožňuje organizáciu dát v štruktúrovanej forme, čím uľahčuje ich rýchlejšie vyhľadávanie, získavanie a analýzu.

  2. Získavanie informácií: Triedené dáta uľahčujú rýchlejšie vyhľadávanie a získavanie informácii. Vyhľadávanie v triedenom zozname je efektívnejšie, pretože môžeme použiť vyhľadávacie algoritmy ako napríklad binárne hľadanie.


Rozsah triediacich algoritmov¶

Triediace algoritmy sa líšia v zložitosti, efektívnosti a vhodnosti pre rôzne typy dát a veľkosti problémov. Môžu byť klasifikované podľa ich základných princípov, ako aj podľa ich časovej a priestorovej zložitosti.

Existujú rôzne triediace algoritmy, od jednoduchých a intuitívnych metód ako Bubble sort a Insert sort po sofistikovanejšie metódy ako Merge sort, Quick sort atď.


Typy triediacich algoritmov¶

Porovnávacie triediace algoritmy sú najbežnejším typom a pracujú porovnávaním jednotlivých prvkov vstupnej kolekcie a ich postupným presúvaním do správneho poradia. Tu sú niektoré z najznámejších porovnávacích triediacich algoritmov na ktoré sa pozriem v tejto práci:

  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort

Testovacia funkcia¶

In [ ]:
import random

generated_data = [random.randint(1, 100) for _ in range(30)]


def test(func):
  data = generated_data.copy()
  print(data)
  func(data)
  print(data)

Bubble Sort¶

Bubble Sort je jednoduchý algoritmus, ktorý opakovane prechádza cez zoznam a porovnáva susedné prvky. Ak sú v nesprávnom poradí, vymenia sa. Tento proces sa opakuje, kým nie sú všetky prvky usporiadané.

Tento algoritmus má časovú zložitosť O(n^2). Je vhodný pre malé zoznamy ale nie je efektívny pre veľké množstvo dát.

In [ ]:
def bubble_sort(arr):
  n = len(arr)
  # swapped = False
  for i in range(n - 1):
    for j in range(0, n - i - 1):
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]
    #     swapped = True
    # if not swapped:
    #   break

test(bubble_sort)
[11, 61, 12, 84, 62, 18, 83, 11, 19, 43, 23, 14, 73, 50, 40, 52, 48, 91, 19, 66, 96, 32, 27, 56, 17, 43, 73, 11, 97, 37]
[11, 11, 11, 12, 14, 17, 18, 19, 19, 23, 27, 32, 37, 40, 43, 43, 48, 50, 52, 56, 61, 62, 66, 73, 73, 83, 84, 91, 96, 97]

Selection Sort¶

Selection Sort funguje tak, že v každom kroku nájde najmenší nepremiestnený prvok a presunie ho na správnu pozíciu. Tento proces sa opakuje, kým nie je celý zoznam usporiadaný.

Časová zložitosť tohto algoritmu je tiež O(n^2), ale môže byť v praxi efektívnejší ako bublinkové triedenie pre veľké zoznamy, pretože má menej výmen.

In [ ]:
def selection_sort(arr):
  for step in range(len(arr)):
    min_index = step

    for i in range(step + 1, len(arr)):
      if arr[i] < arr[min_index]:
        min_index = i
    arr[step], arr[min_index] = arr[min_index], arr[step]

test(selection_sort)
[11, 61, 12, 84, 62, 18, 83, 11, 19, 43, 23, 14, 73, 50, 40, 52, 48, 91, 19, 66, 96, 32, 27, 56, 17, 43, 73, 11, 97, 37]
[11, 11, 11, 12, 14, 17, 18, 19, 19, 23, 27, 32, 37, 40, 43, 43, 48, 50, 52, 56, 61, 62, 66, 73, 73, 83, 84, 91, 96, 97]

Insertion Sort¶

Insertion Sort funguje tak, že postupne vkladá prvky z neusporiadanej časti zoznamu do už usporiadanej časti zoznamu tak, aby výsledný zoznam bol usporiadaný. Tento proces sa opakuje, kým nie sú všetky prvky vložené do usporiadanej časti.

Tento algoritmus má tiež časovú zložitosť O(n^2), ale je efektívnejší pre zoznamy, ktoré sú už čiastočne usporiadané.

In [ ]:
def insertion_sort(arr):
  for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0 and key < arr[j]:
      arr[j + 1] = arr[j]
      j -= 1
    arr[j + 1] = key

test(insertion_sort)
[11, 61, 12, 84, 62, 18, 83, 11, 19, 43, 23, 14, 73, 50, 40, 52, 48, 91, 19, 66, 96, 32, 27, 56, 17, 43, 73, 11, 97, 37]
[11, 11, 11, 12, 14, 17, 18, 19, 19, 23, 27, 32, 37, 40, 43, 43, 48, 50, 52, 56, 61, 62, 66, 73, 73, 83, 84, 91, 96, 97]

Merge Sort¶

Merge Sort je efektívny algoritmus, ktorý využíva princíp rozdelenia a zlúčenia. Postupne delí zoznam na polovice, triedi ich a potom zlúči do výsledného usporiadaného zoznamu.

Tento algoritmus má časovú zložitosť O(n log n), čo ho robí efektívnym pre veľké zoznamy. Jeho hlavnou nevýhodou je potreba dodatočnej pamäte pre zlúčenie podzoznamov.

In [ ]:
def merge_sort(arr):
  if len(arr) > 1:
    mid = len(arr) // 2
    L = arr[:mid]
    R = arr[mid:]
    merge_sort(L)
    merge_sort(R)
    i = j = k = 0
    while i < len(L) and j < len(R):
      if L[i] <= R[j]:
        arr[k] = L[i]
        i += 1
      else:
        arr[k] = R[j]
        j += 1
      k += 1
    while i < len(L):
      arr[k] = L[i]
      i += 1
      k += 1
    while j < len(R):
      arr[k] = R[j]
      j += 1
      k += 1

test(merge_sort)
[11, 61, 12, 84, 62, 18, 83, 11, 19, 43, 23, 14, 73, 50, 40, 52, 48, 91, 19, 66, 96, 32, 27, 56, 17, 43, 73, 11, 97, 37]
[11, 11, 11, 12, 14, 17, 18, 19, 19, 23, 27, 32, 37, 40, 43, 43, 48, 50, 52, 56, 61, 62, 66, 73, 73, 83, 84, 91, 96, 97]

Quick Sort¶

Quick Sort je založené na princípe rozdelenia a zjednotenia podľa pivotu. Zoznam je rozdelený na dve podmnožiny na základe pivotu a potom sú obe podmnožiny triedené rekurzívne.

Tento algoritmus má priemernú časovú zložitosť O(n log n) a je často jedným z najrýchlejších triediacich algoritmov. Jeho efektivita však môže klesať v prípade, že je zoznam veľmi nevyvážený.

In [ ]:
def quick_sort(array, low, high):
  if low < high:
    pivot = array[high]
    i = low - 1
    for j in range(low, high):
      if array[j] <= pivot:
        i += 1
        array[i], array[j] = array[j], array[i]

    array[i + 1], array[high] = array[high], array[i + 1]
    pi = i + 1
    quick_sort(array, low, pi - 1)
    quick_sort(array, pi + 1, high)

test(lambda arr: quick_sort(arr, 0, len(arr) - 1))
[11, 61, 12, 84, 62, 18, 83, 11, 19, 43, 23, 14, 73, 50, 40, 52, 48, 91, 19, 66, 96, 32, 27, 56, 17, 43, 73, 11, 97, 37]
[11, 11, 11, 12, 14, 17, 18, 19, 19, 23, 27, 32, 37, 40, 43, 43, 48, 50, 52, 56, 61, 62, 66, 73, 73, 83, 84, 91, 96, 97]

Vizualizácia triediacich algoritmov¶

Vizualizácia triediacich algoritmov je užitočný nástroj na pochopenie ich fungovania a porovnanie ich efektivity.

In [ ]:
from matplotlib.animation import FuncAnimation
import matplotlib.pyplot as plt
import matplotlib as mp
import random

n = 15
delay = 100
arr = [i for i in range(1, n + 1)]
random.shuffle(arr)

def show(generator):
  data = []
  for i in generator(arr.copy()):
    data.append(i.copy())

  plt.style.use('fivethirtyeight')
  plt.rcParams['animation.html'] = 'jshtml'
  # plt.rcParams["figure.dpi"] = 150
  # plt.ioff()

  fig, ax = plt.subplots()
  rects = ax.bar(range(n), arr, align='edge', color=(0.54, 0.04, 0.04))

  ax.set_xlim(0, n)
  ax.set_ylim(0, int(1.1 * n))

  text = ax.text(0.01, 0.95, '', transform=ax.transAxes)

  iteration = [0]

  def animate(A, rects, iteration):
    for rect, val in zip(rects, A):
      rect.set_height(val)

    text.set_text(f'iterations : {iteration[0]}')
    iteration[0] += 1

  return FuncAnimation(
    fig,
    func=animate,
    fargs=(rects, iteration),
    frames=data,
    interval=delay,
  )

Vizualizácia Bubble Sortu¶

In [ ]:
def bubblesort(arr):
  n = len(arr)
  for i in range(n - 1):
    swapped = False
    for j in range(0, n - i - 1):
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]
        swapped = True
        yield arr
    if swapped == False:
      break

show(bubblesort)
Out[ ]:
No description has been provided for this image
No description has been provided for this image

Vizualizácia Selection Sortu¶

In [ ]:
def selectionsort(arr):
  for step in range(len(arr)):
    min_idx = step

    for i in range(step + 1, len(arr)):
      if arr[i] < arr[min_idx]:
        min_idx = i
    (arr[step], arr[min_idx]) = (arr[min_idx], arr[step])
    yield arr

show(selectionsort)
Out[ ]:
No description has been provided for this image
No description has been provided for this image

Vizualizácia Insertion Sortu¶

In [ ]:
def insertionsort(arr):
  for j in range(1, len(arr)):
    key = arr[j]
    i = j - 1

    while i >= 0 and arr[i] > key:
      arr[i + 1] = arr[i]
      i -= 1
      yield arr
    arr[i + 1] = key
    yield arr

show(insertionsort)
Out[ ]:
No description has been provided for this image
No description has been provided for this image

Vizualizácia Merge Sortu¶

In [ ]:
def mergesort(A, start, end):
  if end <= start:
    return

  mid = start + ((end - start + 1) // 2) - 1

  yield from mergesort(A, start, mid)
  yield from mergesort(A, mid + 1, end)
  yield from merge(A, start, mid, end)


def merge(A, start, mid, end):
  merged = []
  leftIdx = start
  rightIdx = mid + 1

  while leftIdx <= mid and rightIdx <= end:
    if A[leftIdx] < A[rightIdx]:
      merged.append(A[leftIdx])
      leftIdx += 1
    else:
      merged.append(A[rightIdx])
      rightIdx += 1

  while leftIdx <= mid:
    merged.append(A[leftIdx])
    leftIdx += 1

  while rightIdx <= end:
    merged.append(A[rightIdx])
    rightIdx += 1

  for i in range(len(merged)):
    A[start + i] = merged[i]
    yield A


show(lambda a: mergesort(a, 0, len(a) - 1))
Out[ ]:
No description has been provided for this image
No description has been provided for this image

Vizualizácia Quick Sortu¶

In [ ]:
def quicksort(a, l, r):
  if l >= r:
    return
  x = a[l]
  j = l
  for i in range(l + 1, r + 1):
    if a[i] <= x:
      j += 1
      a[j], a[i] = a[i], a[j]
    yield a
  a[l], a[j] = a[j], a[l]
  yield a

  yield from quicksort(a, l, j - 1)
  yield from quicksort(a, j + 1, r)

show(lambda a: quicksort(a, 0, len(a) - 1))
Out[ ]:
No description has been provided for this image
No description has been provided for this image

Benchmarking a porovnanie¶

Benchmarking je dôležitý proces pri hodnotení výkonnosti triediacich algoritmov. Pomáha porovnať rôzne algoritmy podľa ich efektivity a vhodnosti pre konkrétne použitie.

Úvod do benchmarkingu¶

Benchmarking zahŕňa vykonávanie rôznych experimentov s triediacimi algoritmami a zaznamenávanie ich výkonnosti podľa rôznych metrík, ako sú čas trvania triedenia, pamäťové nároky a stabilita algoritmu.

Návrh benchmarkových experimentov¶

Dôležitou súčasťou benchmarkingu je správne navrhnutie experimentov. To zahŕňa vytvorenie rôznych testovacích sád s rôznymi typmi vstupných dát, ako aj rôznymi veľkosťami vstupov.

Implementácia benchmarkingu¶

Po navrhnutí experimentov je potrebné implementovať benchmarkingový kód, ktorý spustí rôzne triediace algoritmy na testovacích dátach a zaznamená ich výsledky.

Porovnanie výsledkov¶

Po vykonaní benchmarkingových experimentov je čas na porovnanie výsledkov a zhodnotenie výkonnosti jednotlivých algoritmov. Pri porovnávaní algoritmov by sa malo zohľadniť niekoľko faktorov, vrátane:

  • Čas triedenia.
  • Pamäťové nároky.
  • Stabilita a robustnosť.

Implementácia¶

Importy¶

In [ ]:
import random
import time
from statistics import mean
import pandas as pd
import matplotlib.pyplot as plt
from tqdm import tqdm

Nastavenie testovacích dát¶

In [ ]:
velkosti_testovacich_sad = [x for x in range(0, 3200, 200)]
pocet_opakovani_pre_jednu_velkost = 1

Vytvorenie dataframe-u a testovacích dát¶

In [ ]:
df = pd.DataFrame()
df['Velkost sady'] = velkosti_testovacich_sad
test_arrays = {i: [random.randint(1, 5000) for _ in range(i)] for i in velkosti_testovacich_sad}

Visualizačná funkcia¶

In [ ]:
def visualise(name):
  global df
  # plt.figure(figsize=(10, 7))
  plt.plot(df['Velkost sady'], df[name], label=name)
  plt.legend()
  plt.title('Porovnanie časových náročností rôznych triedianích algoritmov')
  plt.xlabel('Veľkosť sady (n)')
  plt.ylabel('Čas (s)')
  plt.show()

Benchmarkovacia funkcia¶

In [ ]:
def benchmark(func, name):
  global velkosti_testovacich_sad, test_arrays, df

  times = []
  temp = []
  print(f'Benchmark pre {name}')
  for i in tqdm(velkosti_testovacich_sad, desc='Prebieha benchmarkovanie:'):
    for _ in range(pocet_opakovani_pre_jednu_velkost):
      start = time.time()
      func(test_arrays[i].copy())
      end = time.time()
      temp.append(end - start)
    times.append(mean(temp))
    temp = []
  df[name] = times
  visualise(name)

Benchmark Bubble Sortu¶

In [ ]:
benchmark(bubble_sort, 'Bubble Sort')
Benchmark pre Bubble Sort
Prebieha benchmarkovanie:: 100%|██████████| 16/16 [00:03<00:00,  5.20it/s]
No description has been provided for this image

Benchmark Selection Sortu¶

In [ ]:
benchmark(selection_sort, 'Selection Sort')
Benchmark pre Selection Sort
Prebieha benchmarkovanie:: 100%|██████████| 16/16 [00:01<00:00, 12.85it/s]
No description has been provided for this image

Benchmark Insertion Sortu¶

In [ ]:
benchmark(insertion_sort, 'Insertion Sort')
Benchmark pre Insertion Sort
Prebieha benchmarkovanie:: 100%|██████████| 16/16 [00:01<00:00, 12.52it/s]
No description has been provided for this image

Benchmark Merge Sortu¶

In [ ]:
benchmark(merge_sort, 'Merge Sort')
Benchmark pre Merge Sort
Prebieha benchmarkovanie:: 100%|██████████| 16/16 [00:00<00:00, 231.86it/s]
No description has been provided for this image

Benchmark Quick Sortu¶

In [ ]:
benchmark(lambda arr: quick_sort(arr, 0, len(arr) - 1), 'Quick Sort')
Benchmark pre Quick Sort
Prebieha benchmarkovanie:: 100%|██████████| 16/16 [00:00<00:00, 432.44it/s]
No description has been provided for this image

Uloženie výsledkov do data.csv a ich zobrazenie¶

In [ ]:
# df.to_csv('data.csv', index=False)
pd.set_option('display.precision', 4)
df.head(None)
Out[ ]:
Velkost sady Bubble Sort Selection Sort Insertion Sort Merge Sort Quick Sort
0 0 0.0000 0.0000 0.0000 0.000 0.000
1 200 0.0010 0.0010 0.0010 0.001 0.001
2 400 0.0070 0.0040 0.0030 0.000 0.000
3 600 0.0190 0.0195 0.0085 0.001 0.001
4 800 0.0370 0.0310 0.0180 0.001 0.001
... ... ... ... ... ... ...
11 2200 0.2706 0.1196 0.1265 0.005 0.003
12 2400 0.3145 0.1376 0.1456 0.006 0.006
13 2600 0.3749 0.1631 0.1719 0.005 0.004
14 2800 0.5163 0.1871 0.1972 0.012 0.004
15 3000 0.5098 0.2147 0.2231 0.012 0.004

16 rows × 6 columns

Ich celkové porovnanie¶

In [ ]:
# df = pd.read_csv('data.csv')

plt.figure(figsize=(10, 7))
for i in df.columns[1:]:
  plt.plot(df['Velkost sady'], df[i], label=i)
plt.legend()
plt.title('Porovnanie časových náročností rôznych triedianích algoritmov')
plt.xlabel('Veľkosť sady (n)')
plt.ylabel('Čas (s)')
plt.show()
No description has been provided for this image

Záver¶

V tomto Jupyter Notebook sme pracovali s rôznymi triediacimi algoritmami a vizualizovali sme ich fungovanie. Začali sme s implementáciou algoritmov ako Bubble Sort, Selection Sort, Insertion Sort, Merge Sort a Quick Sort. Následne sme vytvorili vizualizácie týchto algoritmov pomocou animácií.

Okrem toho sme tiež vykonali benchmarking týchto algoritmov a porovnali sme ich výkonnosť na rôznych veľkostiach vstupných dát. Výsledky sme zaznamenali do dataframe-u a vizualizovali sme ich pomocou grafu.

Celkovo sme v tomto Jupyter Notebook demonštrovali implementáciu triediacich algoritmov, vizualizáciu ich fungovania a benchmarking ich výkonnosti.

Ukazalo sa že najrýchlejší algoritmus je Quick Sort a Merge Sort ktoré má priemernú časovú zložitosť O(n log n) a sú často jednými z najrýchlejších triediacich algoritmov.

Ďakujem za pozornosť!¶